package __2_recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/*

八皇后问题：
在一个8*8的国际象棋上摆上八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列、同一斜线，
问有多少种摆法？

1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1

这里想用枚举法把每种摆法遍历一遍，再判断是否处于同一行、同一列、同一斜线，否，则count++，
那么需要枚举8的8次方种情况，需要八层for循环嵌套，运算量太大

换个思路，一个长度为8的数组，第i行代表第i个索引值，每个索引值对应的数的值就代表列数。
那么就是要我们求02461357(对应上图)的排列数，不过是有条件的排，
比如相邻两个值之差必须大于等于2，即0不能与1相邻，1也能和2相邻，2也不能和3相邻，3也不能和4相邻...
不不不，我tm才发现，这样是有问题的，02461357是不行的，0和7在同一斜线啊



 */

public class __4_EightQueens {

    // 定义辅助集合
    static HashSet<Integer> cols = new HashSet<>();
    static HashSet<Integer> diags1 = new HashSet<>();
    static HashSet<Integer> diags2 = new HashSet<>();
    public static void main(String[] args) {
        int count = 0;
        for (int[] arr : eightQueens()) {
            System.out.println(Arrays.toString(arr));
            count++;
        }
        System.out.println(count);
    }

    // 方法二：回溯法
    public static List<int[]> eightQueens() {
        ArrayList<int[]> result = new ArrayList<>();
        int[] solution = new int[8];
        Arrays.fill(solution, -1); // 初始填充-1
        // 传入行号0，开始调用
        backtrack(result, solution, 0);
        return result;
    }

    // 定义一个回溯方法
    private static void backtrack(ArrayList<int[]> result, int[] solution, int row){
            if (row >= 8){
                result.add(Arrays.copyOf(solution, 8));
            } else {
                // 遍历每一列，考察可能的皇后位置
                for (int column = 0; column < 8; column ++){
                    if (cols.contains(column))
                        continue;
                    int diag1 = row - column;
                    if (diags1.contains(diag1))
                        continue;
                    int diag2 = row + column;
                    if (diags2.contains(diag2))
                        continue;
                    solution[row] = column;    // 当前位置可以放置皇后
                    cols.add(column);
                    diags1.add(diag1);
                    diags2.add(diag2);
                    // 递归调用，找下一行的皇后
                    backtrack(result, solution, row + 1);
                    // 回溯状态
                    solution[row] = -1;
                    cols.remove(column);
                    diags1.remove(diag1);
                    diags2.remove(diag2);
                }
            }
        }
}